class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        vector<int> path;
        sort(nums.begin(), nums.end());
        auto dfs = [&](this auto&& dfs, int i) {
            if (i == n) {
                ans.push_back(path);
                return;
            }

            int x = nums[i];
            path.push_back(x);
            dfs(i + 1);
            path.pop_back();
            i++;
            while (i < n && nums[i] == x) {
                i++;
            }
            dfs(i);
        };
        dfs(0);
        return ans;
    }
};